import java.util.LinkedList;

public class AAStar {
	// Generates the heuristic value for the path.
	// HEURISTIC:	-h = Minimum of [outgoing edge plus destination node food consumed] from the final node in the path  
	//				-Unless path length is larger than the maze in which case h=-Integer.MAX_VALUE (just in case)
	public static int generateH(Maze maze, CostedPath path) {
		if (path.path.size() > 5 * maze.getNodes().size()) {
			return Integer.MAX_VALUE;
		}
		
		// If it's a solution, there is zero cost to get to the solution.
		if (path.path.get(path.path.size() - 1).getType() == MazeNode.Type.TREASURE) {
			return 0;
		}
		
		MazeEdges adjacentEdges = maze.getAdjacencyEdges(path.path.get(path.path.size() - 1));
		int h = Integer.MAX_VALUE;
		int candidateH;
		for (MazeEdge edge : adjacentEdges) {
			candidateH = edge.getCost() + edge.getDestination().getFood_consume();
			if (candidateH < h) {
				h = candidateH;
			}
		}
		
		return h;
	}
	
	// Returns the node from open which should be expanded next.
	public static SearchNode nextNodeToExpand(LinkedList<SearchNode> open, LinkedList<SearchNode> closed, Maze maze) {
		return open.get(0);
	}
	
	// Adds the children of current to open and reorders open if required.
	public static void addChildrenToOpen(SearchNode current, LinkedList<SearchNode> open, LinkedList<SearchNode> closed, Maze maze) {
		// Find the last node in the path and find its outedges
		MazeNode currentNode = current.getIdentifier().path.get(current.getIdentifier().path.size() - 1);
		MazeEdges currentOutEdges = maze.getAdjacencyEdges(currentNode);
		
		// Create new search nodes for each of the current node's outedges and add them to the end of open
		SearchNode newSearchNode;
		for (MazeEdge edge : currentOutEdges) {
			newSearchNode = createNewSearchNode(maze, current, edge, edge.getDestination());
			if (isValidChild(newSearchNode, maze)) {
				open.add(newSearchNode);
			}
		}
		
		// Sort open by decreasing f-value
		sort(open);
		
		// We're done. Go back to the graphsearch algorithm.
		return;
	}
	
	// Generates a new SearchNode
	// (for use by addChildrenToOpen)
	private static SearchNode createNewSearchNode(Maze maze, SearchNode oldNode, MazeEdge edge, MazeNode node) {
		CostedPath oldPath = oldNode.getIdentifier();
		CostedPath newPath = new CostedPath(new MazeNodes(), new MazeEdges());
		
		newPath.path.addAll(oldPath.path);
		newPath.path.add(node);
		newPath.edges.addAll(oldPath.edges);
		newPath.edges.add(edge);
		
		return new SearchNode(newPath, generateH(maze, newPath));
	}
	
	private static boolean isValidChild(SearchNode node, Maze maze) {
		if (node.getIdentifier().getFq() < 0) {
			return false;
		}
		if (node.isSolution()) {
			return true;
		}
		
		// Enforce the depth limit
		if (node.getIdentifier().path.size() > 5 * maze.getNodes().size()) {
			return false;
		}
		
		// Check if path contains a positive-weighted cycle - if it does, we can skip it
		CostedPath path = node.getIdentifier();
		for (int i = 0; i < path.path.size() - 1; i++) {
			if (path.path.get(i).equals(path.path.get(path.path.size() - 1))) {
				int cycleWeight = 0;
				for (int j = i; j < path.path.size() - 1; j++) {
					cycleWeight += path.edges.get(j).getCost() + path.path.get(j + 1).getFood_consume() - path.path.get(j + 1).getFood_gain();
				}
				if (cycleWeight >= 0) {
					return false;
				}
			}
		}
		
		// If we get here, it's fine
		return true;
	}
	
	// Sorts the list of SearchNodes by decreasing f-value using Insertion Sort
	// (The list will generally be small and/or mostly sorted so Insertion Sort should perform well.)
	private static void sort(LinkedList<SearchNode> list) {
		int insertLocation;

		for (int firstUnsorted = 1; firstUnsorted < list.size(); firstUnsorted++) {
			// Find where the first unsorted element needs to be inserted
			insertLocation = firstUnsorted - 1;
			while (insertLocation >= 0 && isBetter(list.get(firstUnsorted), list.get(insertLocation))) {
				insertLocation--;
			}
			insertLocation++;
			
			// If insertLocation == firstUnsorted then it's already in the right place. Otherwise, insert it.
			if (firstUnsorted != insertLocation) {
				list.add(insertLocation, list.remove(firstUnsorted));
			}
		}
		
		return;
	}
	
	// Returns whether firstUnsorted is a more promising path than insertLocation
	private static boolean isBetter(SearchNode firstUnsorted, SearchNode insertLocation) {
		if (insertLocation.getF() < firstUnsorted.getF()) {
			return false;
		}
		if (insertLocation.getF() == firstUnsorted.getF() && insertLocation.getG() <= firstUnsorted.getG()) {
			return false;
		}
		
		// Either firstUnsorted has a smaller f value, or the two f values are equal and firstUnsorted has a smaller g value
		return true;
	}
	
}
